package 数据结构专栏.B_链表专栏;

/**
 * @Title abcba -> 检测链表是否是回文
 * @Author zhengqiang.tan
 * @Date 2021/5/20 8:57 PM
 * <p>
 * 智领云面试题 2021年5月20日 周四 做对了
 */
public class 回文链表检测 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(3);
        ListNode n2 = new ListNode(5);
        ListNode n3 = new ListNode(7);
        ListNode n4 = new ListNode(5);
        ListNode n5 = new ListNode(3);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        ListNode list2 = reverseList(n1);
        printList(list2);

        System.out.println(compareList(n1, list2));

    }

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode nextNode = head.next;
        head.next = null;
        ListNode res = reverseList(nextNode);
        nextNode.next = head;
        return res;
    }

    public static boolean compareList(ListNode n1, ListNode n2) {
        boolean flag = false;
        if (n1.val == n2.val) {
            flag = true;
        }
        if (n1.next != null && n2.next != null) {
            flag = compareList(n1.next, n2.next);
        }
        return flag;
    }

    public static void printList(ListNode node) {
        System.out.print(node.val);
        if (node.next != null) {
            printList(node.next);

        }
    }

    // 扩展：
    // 数组转为链表
    // https://zhuanlan.zhihu.com/p/87564492
    public  static ListNode array2NodeList(int [] num) {
      ListNode root = new ListNode(num[0]);
      ListNode other = root;
        for (int i = 1; i < num.length; i++) {
            ListNode temp = new ListNode(num[i]);
            other.next = temp;
            other = temp;

        }
        return root;
    }


    // 扩展：链表转为数组
    public int LinkListSize(ListNode root){
        return  0;
    }



    }
